The invention finds a particularly beneficial application in the field of low-cost cryptography, notably in the field of radio-identification (“Radio Frequency Identification”, or “RFID”).
Radio-identification is a technique for storing and recovering remote data by using markers called radio tags (one also speaks of “RFID tag”). A radio tag comprises an antenna associated with an electronic chip which allows it to receive and to respond to radio requests transmitted from a transmitter-receiver called a reader. A distinction is made between active RFID tags which have a battery allowing them to perform calculations, and passive RFID tags, which use energy provided by the reader. Radio tags are used for example to identify people when the tags are integrated into passports, into transport tickets, or into payment cards, or to identify products as with a bar code. The reader is then a verifier in charge of the authentication of the tags which are entities to be authenticated. In terms of cost, prices vary considerably from one tag to another. It is understood that inexpensive radio-tags are very restricted environments in the sense that they have limited calculation power and storage space which is also severely limited by cost constraints. It is understood furthermore that a passive RFID tag is all the more limited, on account of its power supply, by the type of operations that it can perform.
Nonetheless, recent years have seen proposals to add cryptographic protections on radio-tags so as to combat threats such as cloning of tags, traceability of tags, listening in to exchanges between a tag and a reader, and replaying of such exchanges with the aim of passing a pirate tag off as a valid tag. These protections rely on cryptographic protocols, operation of which requires a certain number of cryptographic primitives able to ensure basic functions required by the protocols. Many security primitives rely on the use of block cipher. Indeed, block cipher primitives are versatile in the sense that they may be used according to various operative modes to construct numerous basic security functions. For example, block cipher primitives are used to construct pseudo-random functions, stream encryption functions, codes for authenticating messages (the term commonly used is the term “MAC” for “Message Authentication Code”), or else hash functions. Whatever operative mode is used, the data processed by a block cipher algorithm are structured as data blocks of predefined size, for example 64 bits, 128 bits.
In restricted devices, such as RFID tags, cryptographic elements, such as for example keys and initialization data, are installed in the factory, during the creation of the tag and are no longer modified thereafter. Thus, when a tag is used in the course of various successive sessions, for example successive sessions of authentication with a reader, the block encryption algorithm is used in the same manner from one session to another, and this may entail security problems. Thus, when the block encryption algorithm is used during each session to generate a pseudo-random string used for example in the course of a process of authentication with the reader, the generation of the same pseudo-random string in the course of the various sessions is contrary to a sought-after property of non-repetition and unpredictability of the strings produced. Indeed, this can compromise the security of authentication.